The presence of convective weather (thunderstorms) in terminal and nearby en route airspace of major airports can have significant impacts on departure operations. Traffic on departure routes impacted by convective weather may be constrained by miles-in-trail (MIT) restrictions to allow controllers the time needed to maneuver individual flights around thunderstorms that pilots wish to avoid. When the workload required to manage traffic flows becomes too great, departure routes may be closed. Departures still on the ground that are scheduled for closed or restricted routes may face significant delays as they wait for clearance on their scheduled route or for a viable reroute to be implemented.
Effective departure management can reduce delays at the most congested airports. Unfortunately, Traffic Management Coordinators (TMCs) often lack the integrated information necessary to effectively manage departures. Therefore, TMCs are left with the difficult task of mentally integrating multiple information sources with flight plans to determine which flights will be impacted and how those flights should be rerouted if necessary. To effectively reroute one or more flights, a TMC should know which routes are available, how those routes impact other departure fixes and routes, the additional flying time required to fly those routes, and a multitude of other factors. Moreover, when selecting reroutes, TMCs must balance competing priorities such as reducing flying time and reducing congestion. In addition, TMCs should quickly coordinate the selected reroutes with multiple control facilities, as well as with flight operators.
Attempts have been made to provide computed departure rerouting solutions based on formulating departure routing as a scheduling problem. For example, Capozzi et al., “Towards Optimal Routing and Scheduling of Metroplex Operations,” AIAA Aviation Technology, Integration, and Operations Conference, 21-23 Sep. 2009, Hilton Head, S.C., describes departure scheduling problems for a metroplex, where a metroplex is defined as two or more airports within the same Terminal Radar Approach Control sharing airspace resources. Scheduling problems, or, more specifically, job scheduling problems, are typically formulated as a set of binary decisions that determine the coordinated utilization of shared resources. Inclusion of timing constraints results in a Mixed-Integer Linear Programming (MILP) problem formulation. Given the combinatorial nature of the decisions, the job scheduling problem is of the class of non-deterministic polynomial-time hard (NP-hard) problems, and no polynomial time algorithm for solving such a problem is currently known.
The computation time of problems of this type is dependent on the number of binary variables, where small increases in the problem size can yield large increases in computation time, an effect commonly referred to as “combinatorial explosion.” Thus, rerouting solutions based on this type of problem formulation often cannot be used for real world applications in which the number of variables outstrips the ability of such formulations to generate solutions in real time.